package com.yequan.leetcode.trie.findWords_212;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : Administrator
 * @date : 2020/5/1
 */
public class FindWords {

    private char[][] board;
    private int row;
    private int column;
    private boolean[][] marked;
    private String word;
    private int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) {
                ans.add(word);
            }
        }
        return ans;
    }

    /**
     * 深度优先于回溯法
     * 遍历二维数组,用深度优先算法找到相同的前缀的字符, 直到找不到,开始回溯查找,
     * 将访问过的位置存入对应的二维数组中,避免重复查找
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        if (null == board) {
            return false;
        }
        row = board.length;
        if (row == 0) {
            return false;
        }
        column = board[0].length;
        if (row * column < word.length()) {
            return false;
        }
        this.board = board;
        this.word = word;
        marked = new boolean[row][column];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (searchWord(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 深度优先搜索+回溯搜索符合条件代码
     *
     * @param i
     * @param j
     * @param index
     * @return
     */
    private boolean searchWord(int i, int j, int index) {
        if (index == word.length() - 1) {
            return board[i][j] == word.charAt(index);
        }
        if (board[i][j] == word.charAt(index)) {
            marked[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newX = i + directions[k][0];
                int newY = j + directions[k][1];
                if (isLegal(newX, newY) && !marked[newX][newY]) {
                    if (searchWord(newX, newY, index + 1)) {
                        return true;
                    }
                }
            }
            marked[i][j] = false;
        }
        return false;
    }

    /**
     * 边界判断
     *
     * @param x
     * @param y
     * @return
     */
    private boolean isLegal(int x, int y) {
        return (x >= 0 && x < row) && (y >= 0 && y < column);
    }

}
